#pragma once
#include <iostream>
#include <string>
#include <sstream>
#include "Node.h"
using namespace std;

template<class INFO>
class Queue
{


public:

	Node<INFO> *head;
	Node<INFO> *tail;

	Queue()
	{
		head = tail = nullptr;
	}

	bool emptyqueue(){ return head == nullptr; }

	INFO GetInfo(){return INFO; }

	void add_at_head(INFO info)
	{
		if (head == nullptr)
		{
			head = tail = new Node<INFO>(info);
		}
		else
		{
			Node<INFO> *n = new Node<INFO>(info);
			n->next = head;
			head = n;
		}
	}

	Node<INFO>* back()
	{
		if (head != nullptr)
		{
			return tail;
		}

		else
		{
			throw exception("ForwardList::back, empty list");
		}

	}

	string str()
	{
		ostringstream oss;
		Node<INFO> *n = head;

		if (n == nullptr)
		{
			return " ";
		}

		do
		{
			oss << n->info << endl;
			n = n->next;
		} while (n != nullptr);

		return oss.str();
	}

	Node<INFO> * NodeBefore(Node<INFO> *n)
	{
		Node <INFO> *b = head;
		do
		{
			if (b->next == n)
			{
				return b;
			}
			b = b->next;
		} while (b != nullptr);

		return nullptr;
	}

	void remove(Node<INFO> * d)
	{
		Node<INFO> * b = nullptr;

		if (d == nullptr)
		{
			return;
		}

		else if (head == nullptr)
		{
			return;
		}

		else if (d == head)
		{
			head = head->next;
			delete d;
			if (head == nullptr)
			{
				tail = nullptr;
			}
		}

		else if (d == tail)
		{
			b = this->NodeBefore(d);
			b->next = nullptr;
			tail = b;
			delete d;
		}

		else
		{
			b = this->NodeBefore(d);
			b->next = d->next;
			delete d;
		}
	}

	Node<INFO> * search(INFO info)
	{
		Node <INFO> *b = head;
		do
		{
			if (b->info == info)
			{
				return b;
			}
			b = b->next;
		} while (b != nullptr);

		return nullptr;
	}

	void clear()
	{
		if (head == nullptr)
		{
			throw exception("ForwardList::clear, empty list");
		}

		Node<INFO> *c = head;
		do
		{
			Node<INFO> *tmp = c;
			c = c->next;
			delete tmp;

		} while (c != nullptr);

		head = tail = nullptr;

	}

	~Queue()
	{
		Node<INFO> * n = head;
		Node<INFO> * d = nullptr;
		while (n != nullptr)
		{
			d = n;
			n = n->next;
			delete d;
		}
	}
};

